import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/9/8 上午 09:57
 */
public class day190908 {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        if (nums.length == 0) {
            return new ArrayList<>();
        }
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        int length = nums.length, max, Max = 0, index = 0;
        int[] dp = new int[length];
        int[] sign = new int[length];
        for (int i = 1; i < length; i++) {
            max = 0;
            sign[i] = i;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && (dp[j] + 1) > max) {
                    max = dp[j];
                    dp[i] = max + 1;
                    sign[i] = j;
                }
            }
            if (Max < dp[i]) {
                Max = dp[i];
                index = i;
            }
        }
        while (index != sign[index]) {
            list.add(nums[index]);
            index = sign[index];
        }
        list.add(nums[index]);
        return list;
    }

    public List<Integer> largestDivisibleSubset2(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        if (nums.length == 0) {
            return ans;
        }
        int[] dp = new int[nums.length];
        int[] dp2 = new int[nums.length];
        Arrays.fill(dp, 1);
        Arrays.fill(dp2, -1);
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (dp[i] < dp[j] + 1) {
                        //dp[i]表示以当前值为结尾时的最大整除子集的长度
                        dp[i] = dp[j] + 1;
                        //dp2[i]表示上一个能被自己整除的且整除子集长度最大的 下标
                        dp2[i] = j;
                    }
                }
            }
        }
        int index = 0;
        for (int i = 1; i < nums.length; i++) {
            if (dp[i] > dp[index]) {
                index = i;
            }
        }
        while (index != -1) {
            ans.add(nums[index]);
            index = dp2[index];
        }
        return ans;
    }

    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        if (distance.length == 0) {
            return 0;
        }
        if (start == destination) {
            return 0;
        }
        int sumR = 0;
        int rStart = start;
        int rEnd = destination;
        while (rStart != rEnd) {
            sumR += distance[rStart];
            rStart ++;
            if (rStart >= distance.length) {
                rStart = 0;
            }
        }
        int sumL = 0;
        while (start != destination) {
            start --;
            if (start < 0) {
                start = distance.length - 1;
            }
            sumL += distance[start];
        }
        return Math.min(sumL, sumR);
    }

    public String dayOfTheWeek(int day, int month, int year) {
        String[] week = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
        if (month == 1 || month == 2) {
            month += 12;
            year--;
        }
        int i = (day + 2 * month + 3 * (month + 1) / 5 + year + year / 4 - year / 100 + year / 400) % 7;
        return week[i];
    }

    public int maximumSum(int[] arr) {
        if (arr.length == 0) {
            return 0;
        }
        int[] arrR = new int[arr.length];
        int[] arrL = new int[arr.length];

        int sum = 0;
        int last = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            arrR[i] = sum - last;
            last = Math.min(sum, last);
        }
        sum = 0;
        last = 0;
        for (int i = arr.length - 1; i >= 0; i--) {
           sum += arr[i];
           arrL[i] = sum - last;
           last = Math.min(sum, last);
        }
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arrL[i]);
            max = Math.max(max, arrR[i]);
            if (i > 0 && i + 1 < arr.length) {
                max = Math.max(max, arrR[i - 1] + arrL[i + 1]);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        day190908 day190908 = new day190908();
        System.out.println(day190908.maximumSum(new int[]{-7, 6, 1, 2, 1, 4, -1}));
    }
}
